A hash function is a function which, upon input of an arbitrary-length value, outputs a fixed-length hash value.
Non-patent literatures 3 and 4 describe a hash function that utilizes, as a block cipher encryption function, a compression function constituted using, for example, AES-256. In order that the hash function described in non-patent literatures 3 and 4 satisfies a collision resistance, employed AES-256 must be an idealized block cipher (see non-patent literatures 1 to 3).
This hash function is a hash function which, where a block cipher has an n-bit plaintext length, forms a hash value having a 2n-bit length.
An idealized block cipher is a block cipher selected randomly from a set of all block ciphers having an n-bit plaintext length (block length) and a k-bit key length.
When a hash function H having a w-bit output length satisfies a collision resistance, it signifies that it is difficult to find two different input values M and M′ for which H(M)=H(M′) holds. Strictly, a hash function is considered to satisfy a collision resistance if such input values cannot be found through hash value calculation of 2w/2 times or less.